package sort

/**
归并排序使用了分治思想，将一个大问题分解成小的子问题来解决。归并排序就是通过递归来实现的。
这个递归的公式是每次都将传入的待排序数据序列一分为二，直到变成不能继续分割的最小区间单元，
然后将最小区间单元数据排序后合并起来，最终返回的就是排序好的数据序列了

在这里搭配动态图查看效果更佳：https://visualgo.net/zh/sorting

时间复杂度：O(nlogn)；
空间复杂度：不是原地排序，最多需要和待排序数据序列同样大小的空间，所以空间复杂度是 O(n)；
算法稳定性：不涉及相等元素位置交换，是稳定的排序算法。

*/
func mergeSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	// 获取分区位置
	p := len(nums) / 2
	// 通过递归分区
	left := mergeSort(nums[0:p])
	right := mergeSort(nums[p:])
	// 排序后合并
	return merge(left, right)
}

// 排序合并
func merge(left []int, right []int) []int {
	i, j := 0, 0
	leftLen, rightLen := len(left), len(right)
	// 用于存放结果集
	var result []int
	for {
		// 任何一个区间遍历完，则退出
		if i >= leftLen || j >= rightLen {
			break
		}
		// 对所有区间数据进行排序
		if left[i] <= right[j] {
			result = append(result, left[i])
			i++
		} else {
			result = append(result, right[j])
			j++
		}
	}
	// 如果左侧区间还没有遍历完，将剩余数据放到结果集
	if i != leftLen {
		for ; i < leftLen; i++ {
			result = append(result, left[i])
		}
	}
	// 如果右侧区间还没有遍历完，将剩余数据放到结果集
	if j != rightLen {
		for ; j < rightLen; j++ {
			result = append(result, right[j])
		}
	}
	// 返回排序后的结果集
	return result
}
